googologywikiaorg-20200223-history
User blog:Edwin Shade/Rank-on-Rank Turing Ordinals and Beyond
As most of you are probably aware, the Church-Kleene ordinal represents the supremum of the computable ordinals, yet at the same time is countable. Thus there is a way we may assign a fundamental sequence to this ordinal, namely by defining \(\omega_1^{CK}n\) as being equal to the ordinal associated with the maximum growth rate of an n-state Turing machine, such that the machine in question converts a sequence of n 1's into f(n) 1's, where the head starts out on the leftmost one, and besides this the tape is blank at both output and input states. The ordinal associated with the growth rate of f(n) is be regarded as the ordinal that would be in the subscript of the fast-growing hierarchy to match f(n). It is very plain to see then, that as the first ordinal diagonalizing over the computable ordinals, any function with a growth-rate equivalent to \(f_{\omega_1^{CK}}(n)\) must be an uncomputable function. Now as the supremum of a set of functions, \(f_{\alpha_1}(n),f_{\alpha_2}(n),f_{\alpha_3}(n),...\) is the function \(f_{\alpha_{\omega}}(n)\), we can therefore conclude that the supremum of the fastest-growing function on n-state Turing machines is a function which diagonalizes over Turing machines and has a growth rate equivalent to \(\omega_1^{CK}\) - that function is the busy beaver function, \(\Sigma(n)\). Therefore the statement \(f_{\omega_1^{CK}}(n)\approx\Sigma(n)\) is correct. Leaving the matter of assigning fundamental sequences to every computable ordinal aside, it is also quite clear that we do not even have to assign a fundamental sequence to an ordinal \(\alpha\) for people to agree that a given function f(n) has a growth rate in the fast-growing hierarchy equivalent to \(\alpha\). This is because no matter what means you use to define the fundamental sequence of \(\alpha\), f(n) will always have the same growth rate in relation to neighboring functions, and therefore the same ordinal associated with it. Fundamental sequences may change, but ordinals never will. This is the reason why the following notation should refer to well-defined ordinals, even though I have not put forth a way of creating fundamental sequences for these ordinals As we will observe however, there is one major problem with my idea that I would like help resolving, if it even can be resolved. First, define \(\langle\alpha\rangle\) as the growth-rate, (in the fast-growing hierarchy), of the busy beaver function which diagonalizes over a level-\(\alpha\) Turing machine, (where level-0 is a normal Turing machine). As we've established though, \(\langle0\rangle\) is already equal to \(\omega_1^{CK}\), so you might imagine that this sequence grows at a phenomenally fast rate. Now here is where I introduce Rank-on-Rank Turing ordinals. Let the first ordinal \(\xi\) such that \(\xi=\langle\xi\rangle\) be \(\langle1|0\rangle\) in my notation. \(\langle1|1\rangle\) will be calculated as the growth rate of the busy beaver function over a level-\(\langle1|0\rangle+1\) Turing machine, and so forth, in a process isomorphic to the Veblen function. Soon we reach \(\langle1|0|0|0|0|0...\rangle\), and thus we may use transfinite place markers as in extended Veblen notation to get us further. I define the as the first \(\xi\) such that \(\xi=\langle1@\xi\rangle\). The Problem Up until now the less observant reader may not notice any flaws in my notation, but there is in fact one which is so severe so as to not only cast into oblivion this notation, but also the very notion of Oracle Turing machines altogether as a feasible way of creating a fast-growing function. The issue is that I have not defined enumeration schemes for the set of Turing machines beneath the Nish-Shade Ordinal, and although I need not define fundamental sequences, ennumeration schemes are essential for one large reason. If it is left to the reader to create their own ennumeration scheme they could selectively choose Turing machines which produce a desired result, (that is, they could choose machines which halt or not), and therefore create arbitrarily large values of the Busy Beaver function for oracle Turing machines To create ennumeration schemes however and put the naturals into a bijection with large uncomputable ordinals would require fundamental sequences though for these ordinals. Hence it turns out I cannot actually get away with creating a notation this powerful - or can I ? If you can spot a way to circumvent the innumerable difficulties I will reward you by naming my next largest googologism after you. The Resolution Through Enumeration In order to consider the Nish-Shade Ordinal a well-defined ordinal and give it it's rightful place as one of the largest countable ordinals ever discovered, a bijection between the naturals and all Turing machines with a level equal to or less than the Nish-Shade ordinal will be required. This is possible, but by no means easy. It is my hopes however, that if I spend enough time on lesser enumeration schemes the solution will become clear to me. Enumerating All Level-0 Turing Machines For the set of normal Turing machine, there are BE FIGURED OUT possible rule-sets for an n-state machine. Category:Blog posts